package lanQiaoBei.数学知识.质数;
import java.io.*;
import java.util.*;
/*埃氏筛法求素数
 1、题目：
给定一个正整数n，请你求出1~n中质数的个数。

输入格式
共一行，包含整数n。

输出格式
共一行，包含一个整数，表示1~n中质数的个数。

数据范围
1≤n≤106
输入样例：
8
输出样例：
4
算法思想：
因为每个合数都是由有限个质数相乘得到的，仅筛掉质数的倍数 O(nloglogn)；
* */
public class P3 {
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    final static int N=1000010;
    static int primers[]=new int[N],cnt,n;
    static boolean st[]=new boolean[N];
    static void scan()throws Exception{

    }
    public static void main(String[]args)throws Exception{
           n=Integer.parseInt(br.readLine());
           for(int i=2;i<=n;i++){
               if(st[i])continue;//如果不是质数就进入下一次循环
               primers[cnt++]=i;
               for(int j=i+i;j<=n;j+=i){
                   st[j]=true;
               }
           }
          System.out.print(cnt);
    }
}
